<?php
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class TreeNode {
     public $val = null;
     public $left = null;
     public $right = null;
     function __construct($value) { $this->val = $value; }
 }
class Solution {

    /**
     * @param TreeNode $s
     * @param TreeNode $t
     * @return Boolean
     */
    function isSubtree($s, $t) {
        if(is_null($s) && is_null($t)){
            return true;
        }elseif(is_null($s) || is_null($t)){
            return false;
        }

       if($s->val==$t->val && $this->isSubtreeFull($s->left,$t->left) && $this->isSubtreeFull($s->right,$t->right)){
           return true;
       }
       if($this->isSubtree($s->left,$t)){
           return true;
       }elseif($this->isSubtree($s->right,$t)){
           return true;
       }

        return false;
    }

    function isSubtreeFull($s,$t){
        if(is_null($s) && is_null($t)){
            return true;
        }elseif(is_null($s) || is_null($t)){
            return false;
        }

        if($s->val==$t->val && $this->isSubtreeFull($s->left,$t->left) && $this->isSubtreeFull($s->right,$t->right)){
            return true;
        }
        return false;
    }

    static function  genNode($val,$left=null,$right=null){
        $node= new TreeNode($val);
        $node->val=$val;
        $node->left=$left;
        $node->right=$right;
        return $node;
    }


}